package leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * @Project : AlgorithmLearning
 * @Package : Leetcode
 * @File : Q0438.java
 * @Author : WangRuoyu
 * @Date 2023/11/17 21:54
 */


public class Q0438 {
    private boolean check(int[] cnts, int[] cntp) {
        for (int i = 0; i < cnts.length; i++) {
            if (cnts[i] != cntp[i]) return false;
        }
        return true;
    }

    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        if (s.length() < p.length()) return res;
        int[] cnts = new int[26];
        int[] cntp = new int[26];
        for (int i = 0; i < p.length(); i++) {
            cnts[s.charAt(i) - 'a']++;
            cntp[p.charAt(i) - 'a']++;
        }
        if (check(cnts, cntp)) res.add(0);
        for (int i = 1, j = p.length(); j < s.length(); i++, j++) {
            cnts[s.charAt(i - 1) - 'a']--;
            cnts[s.charAt(j) - 'a']++;
            if (check(cnts, cntp)) res.add(i);
        }
        return res;
    }

    public static void main(String[] args) {
        Q0438 sl = new Q0438();
    }
}